<html>

<head>
<title>Chain of Atom</title>
</head>

<body>
<center>
<h1>CEOI 2001 Day 1 Problem 1</h1>
<h1>Chain of Atoms</h1>
</center>

    <p ALIGN="JUSTIFY">Scientists are investigating a special
    kind of molecule. It is known that the molecule consists of <i>N</i>
    different atoms, labeled from 1 to <i>N</i>, and the structure of the
    molecule is a linear chain. The scientists are equipped with a distance
    meter. At one time, this instrument can measure the distance between any two
    atoms in the molecule. The distance, reported by the instrument, is the
    absolute value of the difference of the two atom positions in the chain. If
    you access no atom for more than three times no damage is done to the
    molecule. If you access one or more atoms four times the molecule gets
    damaged. If you access one or more atoms five times the molecule gets
    destroyed.</p>
    <p ALIGN="JUSTIFY">You are to write a program that
    discovers the complete structure of the molecule by determining the sequence
    of the atoms in the molecule.</p>
    <b><font SIZE="1">
    <p ALIGN="CENTER"><img src="image/12.gif" WIDTH="313" HEIGHT="70"></p>
    </font></b>
    <p ALIGN="CENTER">Figure 1</p>
    <b>
    <h2>Library</h2>
    </b>
    <p ALIGN="JUSTIFY">To operate the distance meter, you are
    given a library meter with three operations:</p>
    <ul>
      <li>Size, to be called once at the beginning, without
        arguments; it returns the value of <i>N</i>. Size must be called before
        any call to Span.</li>
      <li>Span, to be called with two atom labels as
        arguments; it returns the distance between the atoms.</li>
      <li>Answer, to be called at the end, must be used to
        submit your solution. Answer has two integer arguments, <i>i</i> and <i>x</i>,
        and it tells that the label of the atom at position <i>i</i> in the
        molecule is <i>x</i>. For each <i>i</i> (1&lt;= <i>i&lt;= N</i>),
        Answer must be called exactly once in <i>ascending</i> order of <i>i</i>.
        There are always two symmetric solutions, and you can submit any one of
        them.</li>
    </ul>
    <p ALIGN="JUSTIFY">The dialogue between your program and
    the library procedures is logged in the text file chain.out. This log file
    also contains your answer and the error message in case of an error.</p>

    <p><h2>Instruction for Pascal programmers:</h2>
    include the import statement</p>
    <blockquote>
      <blockquote>
        <p>uses meter;</p>
      </blockquote>
    </blockquote>
    <p>in the source code.</p>
    <h2>Instructions for C/C++ programmers:</h2>
    use the instruction</p>
    <blockquote>
      <blockquote>
        <p>#include &quot;meter.h&quot;</p>
      </blockquote>
    </blockquote>
    <p ALIGN="JUSTIFY">in the source code, create a project
    file chain.gpr in the task directory, add the files chain.c (chain.cpp) and
    meter.o into this project, and then <i>compile</i> and/or <i>make</i> your
    program.</p>
    <h2>Experimentation</h2>
    <p ALIGN="JUSTIFY">You can experiment with the library by
    creating a text file chain.in. The file must contain two lines. The first
    line should contain the integer <i>N</i>, the number of atoms. The second
    line should contain a test case: a sequence of the atom labels, consisting
    of <i>N</i> different integers between 1 and <i>N.</p>
    </i><b>
    <h2>Example For Experimentation</h2>
    </b>
    <table BORDER="1" CELLSPACING="1" CELLPADDING="1" WIDTH="378">
      <tr>
        <td WIDTH="50%" VALIGN="TOP">chain.in</td>
        <td WIDTH="50%" VALIGN="TOP">chain.out</td>
      </tr>
      <tr>
        <td WIDTH="50%" VALIGN="TOP">
          5<br>
          1 3 5 2 4</td>
        <td WIDTH="50%" VALIGN="TOP">
          Size=5<br>
          Span(1,2)=3<br>
          Span(1,3)=1<br>
          Span(2,3)=2<br>
          Span(4,5)=2<br>
          Span(1,4)=4<br>
          Span(3,5)=1<br>
          Your Answer:<br>
          1 3 5 2 4<br>
          Max. Access/Atom:<br>
          3</td>
      </tr>
    </table>

    <h2>Constraints</h2>
    <ul>
    </b>
    <li>For the number of atoms, <i>N, </i>we have 5 &lt;= <i>N
      &lt;= </i>10000.</li>
    <li>Accessing any atom by Span more than four times will
      abort your program.</li>
    <li>Your program must not read or write any files.</li>
    <li>For the atom labels <i>x</i> and the atom positions <i>i,</i>
      we have 1 &lt;= <i>i, x &lt;= N.</li>
    </i>
    <li>FreePascal library file names: meter.ppw and
      meter.ow.</li>
    <li>Pascal function declarations:<br>
      function Size: integer;<br>
      function Span(x, y: integer):integer;<br>
      procedure Answer(i, x: integer);</li>
    <li>C/C++ library file names: meter.h and meter.o.<br>
      int Size(void);<br>
      int Span(int x, int y);<br>
      void Answer(int i, int x);</li>
    </ul>
    <h2>Grading</h2>
    <p ALIGN="JUSTIFY">If your answer is correct and no atom
    was accessed more than <i>three</i> times then you obtain full score. If
    your answer is correct but some atom was accessed <i>four </i>times then you
    obtain 50% of the scores. If the answer is incorrect or any atom was
    accessed <i>five </i>times, then you receive 0 score.</p>
    </td>
  </tr>
</table>
</div>
</body>

</html>
